982C - Cut 'em all - CodeForces Solution

#include<bits/stdc++.h>
#define TLE ios::sync_with_stdio(0),cin.tie(0)
#define endl "\n"
#define FILE "a"
#define pb push_back
#define gg exit(0);
#define rt return;
#define bd cout<<"debug"<<endl;
#define db(x) cout<<#x<<':'<<x<<endl;
#define dbb(i,a) cout<<#i<<':'<<i<<' '<<#a<<':'<<a<<' '<<endl;
#define dbbb(i,a,b) cout<<#i<<':'<<i<<' '<<#a<<':'<<a<<' '<<#b<<':'<<b<<endl;
#define TIME cout<<"RuningTime: "<<clock()<<"ms\n";
#define YES cout<<"YES"<<endl;
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define None cout<<-1<<endl;
#define el cout<<endl;
#define x first
#define y second
#define V vector
#define fo(i,j,n) for(register int i = j;i<=n;i++)
#define of(i,n,j) for(register int i = n;i>=j;i--)
#define fe(i,u) for(register int i = h[u];~i;i=ne[i])
#define all(a) a.begin(),a.end()
#define alll(a) a.begin()+1,a.end()
#define ms(a,b) memset(a, b, sizeof(a));
#define tr_len(u) (tr[u].r - tr[u].l + 1)
#define tr_mid (tr[u].l + tr[u].r >> 1)
#define ul (u<<1)
#define ur (u<<1|1)
#define lowbit(x) (x&-x)
#define gcd(a,b) __gcd(a,b)
#define hashset_finetune(p) (p).reserve(1024); (p).max_load_factor(0.25);
#define CLAP 11243
using namespace std;
void clapping() {
	#if CLAP == 1
	srand(time(NULL)+rand());
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
//	freopen("a.in","w",stdout);
	#endif
}
template<class T>inline void read(T &res) {
    char c;T flag = 1;
    while((c = getchar()) < '0' || c > '9') if(c == '-') flag = -1;res = c - '0';
    while((c=getchar())>='0'&&c<='9')res=(res<<1)+(res<<3)+(c^48);res*=flag;
}
typedef pair<int,int> pii;
typedef pair<long,long>pll;
typedef long long ll;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const double eps = 1e-8;
int dy[] = {1,0,-1,0,1,1,-1,-1};
int dx[] = {0,1,0,-1,1,-1,1,-1};
ll qmi(ll a,ll b) {int res = 1;for(;b;b>>=1,a = a * a ) {if(b&1) res = res * a;}return res;} // 注意可能爆ll
template<class T> T exgcd(T a,T b,T &x,T &y) {
	if(b == 0) {x = 1;y = 0;return a;}
	ll d = exgcd(b,a%b,y,x);
	y = y - a / b * x;
	return d;
}
template<class T> T qmul(T a,T b,T p) {
	T res = 0;
	for(;b;b >>= 1,a = (a + a) % p) {
		res = (res + a) % p;
	}
	return res;
}

//-------------------------代码----------------------------

//#define int ll
const int N = 2e5+10;
int n,k;
int h[N],e[N],ne[N],idx;
int dp[N];

void add(int a,int b) {
	e[idx] = b,ne[idx] = h[a],h[a] = idx ++ ;
}

int dfs(int u,int fa) {
	int cnt = 1;
	for(int i = h[u];~i;i=ne[i]) {
		int j = e[i];
		if(j == fa) continue;
		int t = dfs(j,u);
		dp[u] += dp[j];
		if(t % 2 == 0) dp[u] ++ ;
		else cnt += t;
	}
	if(u == 1 && cnt % 2 == 1) dp[u] = -1; 
	return cnt;
}

void solve() {
	cin>>n;
	ms(h,-1);
	fo(i,1,n-1) {
		int a,b;cin>>a>>b;
		add(a,b);add(b,a);
	}
	dfs(1,-1);
	cout<<dp[1]<<endl;;
} 
void main_init() {
//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
}
signed main(){
	clapping();TLE;
	cout<<fixed<<setprecision(12);
	main_init();
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
//	int t;cin>>t;while(t -- )
	solve();
//	{solve(); }
	return 0;
}

/*样例区
构造 二分 贪心 递推 模拟

*/

//------------------------------------------------------------